import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-10-23
 * Time: 8:00
 */
public class test {
    public static int putApple(int M, int N){
        if (M == 0 || M == 1 || N == 1) return 1;
        if (M < N) return putApple(M, M);
        else return putApple(M, N - 1) + putApple(M - N, N);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        if (t < 0 ||  t > 20) {
            System.out.println("数据范围错误。");
            return;
        }
        in.nextLine();
        int[] a = new int[2 * t];
        int j = 0;
        for (int i = 0; i < t; i++){
            String[] arr = in.nextLine().split(" ");
            a[j] = Integer.parseInt(arr[0]);
            a[j + 1] = Integer.parseInt(arr[1]);
            if (a[j] < 0 ||  a[j] > 10 || a[j + 1] < 0 ||  a[j + 1] > 10){
                System.out.println("数据范围错误。");
                return;
            }
            j += 2;
        }
        for (int i = 0; i < a.length; i += 2){
            System.out.println(putApple(a[i], a[i + 1]));
        }
    }
}
